1. Field of the Invention
The present invention relates to providing an implementation of fast vector quantization with topology learning.
2. Description of the Related Art
The problem of topology learning can be defined as: given some high-dimensional data distribution, find a topological structure that closely captures the topology of the data distribution. This problem is closely related to the problem of learning a graph that captures the topological relationships in the data. The goal in topology learning contrasts with that of methods such as Self-Organizing Map (SOM), Growing Cell Structure, Growing Hierarchical Self-Organizing Map, and ISOMAP where the topology of the output space is fixed beforehand. These other methods are mainly concerned with dimensionality reduction. The mappings from the original space to the new space produced by projection methods frequently have topological defects. That is, neighboring points in input spaces may be mapped to far away points in the output or transformed space. Projection methods, however, are especially useful for representing multidimensional data in a form that can be visually inspected.
Learning a topological representation (graph) of a dataset can be used for vector quantization, clustering, link analysis, and indexing for nearest-neighbor and approximate nearest-neighbor searches. Several processes have been proposed for learning general topologies. These can be broadly classified into static (e.g., Neural Gas (NG), and Optimally Topology Preserving Maps (OTPMS)) and constructive architectures (e.g., Growing Neural Gas (GNG), and SAM-SOM). These processes can be seen as attempts to overcome the limitations in the SOM process, including: fixed pre-defined output space topology (SOM uses a regular grid), poor scalability for large topologies, slow learning, and hard to tune parameters. All these methods create topological structures that are more flexible than SOM and thus better capture the topological relationships in the input data distribution. Constructive approaches speed up learning by leveraging hierarchical structures and growing the structure on demand. While most constructive methods use specialized data structures for speeding up learning, SAM-SOM proposes a different approach. It takes advantage of off-the-shelve hierarchical indexing methods to scale to large datasets and number of dimensions. This innovative proposal eliminates the need to develop specialized data structures for speeding up the search for the best matching unit (BMU), a key operation in topology learning processes. Topology-learning processes usually attempt to learn the topology online. As a result, these processes require slow adaptation to the data. With few exceptions (e.g., GNG and SAMSOM), online learning processes use multiple decaying parameters, which lead to relatively slow training. SAM-SOM is the only process that attempts to learn a topological structure with a node for each input data vector. The process use simple rules for creating and pruning connections. It is not clear, however, that these simple rules can approximate well the topology of input data distributions with uneven density and different dimensionalities in different areas of the input space.
Vector quantization is a lossy compression technique that uses a codebook for encoding and decoding data. Vector quantization techniques are aimed at creating small codebooks capable of encoding and decoding data with the smallest possible difference between original and reconstructed data. Vector quantization can also be seen as a special case of clustering. As in clustering, many data records are mapped to a single codevector or cluster. Some applications of vector quantization include speech and image compression. Vector quantizers for high dimensional vector spaces need a large codebook to achieve a small error rate. The Tree-Structured Vector Quantizer (TSVQ) is a popular technique that scales well for large datasets and codebook sizes. Different versions of k-d trees have also been proposed for fast vector quantization. Trees such as k-d trees produce encoders with smaller memory footprint and faster encoding than TSVQ but, in general, they require larger codebooks for achieving the same level of compression of TSVQ.
As the size of the tree (codebook) grows the ability of approaches such as TSVQ and k-d trees to return the actual nearest neighbor to an input vector decreases. That is, the closest codevector (leaf centroid) to a given input may not be the one where the input is mapped to by the tree. The problem becomes more accentuated in axis-parallel approaches like k-d tree, where the partition imposed by the tree at each point is not well aligned with the data distribution principal directions. In general, tree-structured approaches trade speed for higher quantization error for a fixed codebook size when compared with full search approaches such as the LBG process. Some approaches have tried to minimize the impact of the error in the tree assignments by searching multiple paths at the same time or by exploring a learned topological structure to search near-nodes for a better match. Arya and Mount have shown that the latter requires significantly less computation than the standard k-d tree approach for achieving the same level of error. Unfortunately, for a dataset with N input vectors, the RNG* process used in Arya and Mount scales with O(N2), making it unsuitable for large datasets.
A need arises for a technique for performing vector quantization and topology learning that provides improved performance and implementation compared to previous techniques.